Circuit switching is a well known paradigm wherein a physical circuit is established between two terminating endpoints of a switched communication network to provide a communication path therebetween. A circuit switched network in accordance with this paradigm, such as a typical circuit switched telephone network, comprises a plurality of switches and a plurality of trunk groups which connect the switches. In practice, the environment of the circuit switched network is heterogeneous in that the switches may be of different types (e.g. 1AESS, 5ESS, DMS100) and the trunk groups may use different signaling methods (e.g. SS7 and multifrequency).
The switches are connected to the trunk groups in a manner such that there are numerous routing paths between each pair of switches. In practice, the network is either fully-connected or nearly fully-connected. Traffic routing methods are employed in the network for selecting at least one of the paths to provide a physical circuit between a pair of switches. The selected path is based upon data representative of network traffic and at least one predetermined measure of network performance. The traffic routing method attempts to improve the at least one predetermined measure of network performance based upon the network traffic data.
Because of some inherent limitations in the switches, the network traffic data can only be collected from the switches at periodic time intervals. In practice, the network traffic data is collected from the switches at constant time intervals, such as every 5 minutes or every 10 minutes. Hence, a routing path which is optimal for the predetermined measure of network performance cannot be calculated or implemented on a call-by-call basis. The routing optimization can only be performed every T minutes by updating the routing tables at the switches based on the current network traffic status.
Existing state-dependent dynamic routing methods calculate alternate routing paths for each switch pair independently, based upon an average trunk group usage during a previous time interval. The alternate routing paths are ordered, and are attempted sequentially by each call between that switch pair. Using these methods, it is likely that a trunk group having little traffic in the current time interval is used by many alternate routing paths of different switch pairs. Consequently, such a trunk group could become congested in the next time interval. Once it becomes congested, the traffic would be diverted in a subsequent time interval. This leads to the possibility of a cycle occurring.
Examples of existing state-dependent dynamic routing methods are disclosed in U.S. Pat. Nos. 4,669,113 (Ash et al.), 4,704,724 (Krishnan et al.), 5,068,892 (Liranos), 5,101,451 (Ash et al.), and 5,295,183 (Langlois et al.).
U.S. Pat. No. 4,669,113 to Ash et al. discloses a method and a system for dynamical non-hierarchical routing in a telecommunication switching network. Each switch in the network sends idle trunk information to a network controller on a periodic basis when idle trunks are created or removed. This information augments traffic information, which is regularly sent to the network controller, used in developing a plurality of routing path choices. The traffic information includes the number of attempts, the number of blocked calls, and usage counts associated with each originating switch-terminating switch pair. The path choices are ordered based upon a least loaded path approach.
U.S. Pat. No. 4,704,724 to Krishnan et al. discloses a separable, state-dependent routing technique wherein a cost of adding an additional call to a trunk group having calls already in progress is determined for each trunk group. The cost of a multi-link group is the sum of the costs of the trunk groups on the route. For each call, the cost of each potential route is calculated, and the call is carried on the least-cost route.
U.S. Pat. No. 5,068,892 to Livanos recognizes the possibility of prior art systems creating conflicting network management data where a circuit group is to be used for a number of different alternative routes. A method is disclosed wherein a number of reservation levels are defined an alternately-routed traffic is controlled when the number of idle circuits in a route falls below a predetermined number. When the number of idle circuits falls below a second level, both directly-routed and alternately-routed traffic on a route are made subject of control. When an excessive number of circuits, relative to the number of idle circuits, are occupied by incoming traffic, incoming load control may be activated to control incoming traffic from another exchange.
U.S. Pat. No. 5,101,451 to Ash et al. discloses a dynamic routing method based upon two or more thresholds associated with the number of trunks that must be available before various services are allowed to use an available trunk in a particular trunk group. A lower threshold is provided to maintain traffic capacity for key services that are below their respective objective loads. A higher threshold is provided to maintain traffic capacity for all services which are below their respective object loads.
U.S. Pat. No. 5,295,183 to Langlois et al. discloses a congestion control method for a telecommunications system based upon the following information: the number of trunks in a considered outgoing trunk group, the number of occupied trunks in the considered outgoing trunk group, the total average call intensity for the considered outgoing trunk group, the average time per conversation, the time period over which the information is collected, and the expected number of idle trunk lines needed in the trunk group for other than alternately routed calls. Employing this information, the most likely alternate routes are determined and stored within switches in the telecommunication system.